<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>bit_vector</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>bit_vector</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "containers.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "type.gif" Alt=""   WIDTH = "194"  HEIGHT = "39" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: containers</TD>
<TD Align=right VAlign=top><b>Component type</b>: type</TD>
</TR>
</Table>

<h3>Description</h3>
A <tt>bit_vector</tt> is essentially a
<tt><A href="Vector.html">vector</A>&lt;bool&gt;</tt>: it is a
<A href="Sequence.html">Sequence</A> that has the same interface as
<tt><A href="Vector.html">vector</A></tt>.  The main difference is
that <tt>bit_vector</tt> is optimized for space efficiency.  A
<tt>vector</tt> always requires at least one byte per element, but a
<tt>bit_vector</tt> only requires one bit per element.
<P>
<b>Warning</b>: The name <tt>bit_vector</tt> will be removed in a future release
of the STL.  The only reason that <tt>bit_vector</tt> is a separate class,
instead of a template specialization of <tt>vector&lt;bool&gt;</tt>, is that this
would require partial specialization of templates.  On compilers that
support partial specialization, <tt>bit_vector</tt> is a specialization of
<tt>vector&lt;bool&gt;</tt>.  The name <tt>bit_vector</tt> is a <tt>typedef</tt>.  This <tt>typedef</tt>
is not defined in the C++ standard, and is retained only for backward
compatibility.
<h3>Example</h3>
<pre>
bit_vector V(5);
V[0] = true;
V[1] = false;
V[2] = false;
V[3] = true;
V[4] = false;

for (bit_vector::iterator i = V.begin(); i &lt; V.end(); ++i)
  cout &lt;&lt; (*i ? '1' : '0');
cout &lt;&lt; endl;
</pre>
<h3>Definition</h3>
Defined in the standard header <A href="vector">vector</A>, and in the nonstandard
backward-compatibility header <A href="bvector.h">bvector.h</A>.
<h3>Template parameters</h3>
None. <tt>Bit_vector</tt> is not a class template.
<h3>Model of</h3>
<A href="RandomAccessContainer.html">Random access container</A>,
<A href="BackInsertionSequence.html">Back insertion sequence</A>.
<h3>Type requirements</h3>
None.
<h3>Public base classes</h3>
None.
<h3>Members</h3>
<Table border>
<TR>
<TH>
Member
</TH>
<TH>
Where defined
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>value_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The type of object stored in the bit_vector: <tt>bool</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference</tt>
</TD>
<TD VAlign=top>
<tt>bit_vector</tt>
</TD>
<TD VAlign=top>
A proxy class that acts as a reference to a single bit.  See below
   for details.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const reference to <tt>value_type</tt>.  In <tt>bit_vector</tt> this is simply defined
   to be <tt>bool</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
An unsigned integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>difference_type</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
A signed integral type.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Iterator used to iterate through a <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Const iterator used to iterate through a <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Iterator used to iterate backwards through a <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Const iterator used to iterate backwards through a <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator begin()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the beginning of the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator end()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns an <tt>iterator</tt> pointing to the end of the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator begin() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the beginning of the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_iterator end() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_iterator</tt> pointing to the end of the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator rbegin()</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>reverse_iterator</tt> pointing to the beginning of the
   reversed bit_vector.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reverse_iterator rend()</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>reverse_iterator</tt> pointing to the end of the
   reversed bit_vector.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator rbegin() const</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_reverse_iterator</tt> pointing to the beginning of the
   reversed bit_vector.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reverse_iterator rend() const</tt>
</TD>
<TD VAlign=top>
 <A href="ReversibleContainer.html">Reversible Container</A>
</TD>
<TD VAlign=top>
Returns a <tt>const_reverse_iterator</tt> pointing to the end of the
   reversed bit_vector.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the number of elements in the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type max_size() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Returns the largest possible size of the <tt>bit_vector</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type capacity() const</tt>
</TD>
<TD VAlign=top>
<tt>bit_vector</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bool empty() const</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
<tt>true</tt> if the <tt>bit_vector</tt>'s size is <tt>0</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference operator[](size_type n)</tt>
</TD>
<TD VAlign=top>
 <A href="RandomAccessContainer.html">Random Access Container</A>
</TD>
<TD VAlign=top>
Returns the <tt>n</tt>'th element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference operator[](size_type n) const</tt>
</TD>
<TD VAlign=top>
 <A href="RandomAccessContainer.html">Random Access Container</A>
</TD>
<TD VAlign=top>
Returns the <tt>n</tt>'th element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bit_vector()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Creates an empty bit_vector.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bit_vector(size_type n)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a bit_vector with <tt>n</tt> elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bit_vector(size_type n, bool t)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a bit_vector with <tt>n</tt> copies of <tt>t</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bit_vector(const bit_vector&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The copy constructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template &lt;class <A href="InputIterator.html">InputIterator</A>&gt;
bit_vector(InputIterator, InputIterator)
<A href="#1">[1]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Creates a bit_vector with a copy of a range.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>~bit_vector()</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The destructor.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>bit_vector&amp; operator=(const bit_vector&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
The assignment operator
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void reserve(size_t)</tt>
</TD>
<TD VAlign=top>
<tt>bit_vector</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference front()</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference front() const</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Returns the first element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>reference back()</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>const_reference back() const</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Returns the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void push_back(const T&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Inserts a new element at the end.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void pop_back()</tt>
</TD>
<TD VAlign=top>
 <A href="BackInsertionSequence.html">Back Insertion Sequence</A>
</TD>
<TD VAlign=top>
Removes the last element.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void swap(bit_vector&amp;)</tt>
</TD>
<TD VAlign=top>
 <A href="Container.html">Container</A>
</TD>
<TD VAlign=top>
Swaps the contents of two bit_vectors.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void swap(bit_vector::reference x,
          bit_vector::reference y)
</pre>
</TD>
<TD VAlign=top>
<tt>bit_vector</tt>
</TD>
<TD VAlign=top>
See below.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>iterator insert(iterator pos, bool x)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
template &lt;class <A href="InputIterator.html">InputIterator</A>&gt;
void insert(iterator pos,
            InputIterator f, InputIterator l)
<A href="#1">[1]</A>
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts the range <tt>[f, l)</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void insert(iterator pos, 
            size_type n, bool x)
</pre>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Inserts <tt>n</tt> copies of <tt>x</tt> before <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void erase(iterator pos)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the element at position <tt>pos</tt>.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void erase(iterator first, iterator last)</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases the range <tt>[first, last)</tt>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void clear()</tt>
</TD>
<TD VAlign=top>
 <A href="Sequence.html">Sequence</A>
</TD>
<TD VAlign=top>
Erases all of the elements.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator==(const bit_vector&amp;, 
                const bit_vector&amp;)
</pre>
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Tests two bit_vectors for equality.  This is a global function, not
   a member function.
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
bool operator&lt;(const bit_vector&amp;, 
               const bit_vector&amp;)
</pre>
</TD>
<TD VAlign=top>
 <A href="ForwardContainer.html">Forward Container</A>
</TD>
<TD VAlign=top>
Lexicographical comparison.  This is a global function, not
   a member function.
</TD>
</tr>
</table>
<h3>New members</h3>
These members are not defined in the 
<A href="RandomAccessContainer.html">Random access container</A> 
and <A href="BackInsertionSequence.html">Back insertion sequence</A>
requirements, but are specific to <tt>vector</tt>.
<Table border>
<TR>
<TH>
Member
</TH>
<TH>
Description
</TH>
</TR>
<TR>
<TD VAlign=top>
<tt>reference</tt>
</TD>
<TD VAlign=top>
A proxy class that acts as a reference to a single bit; the reason it
   exists is to allow expressions like <tt>V[0] = true</tt>.  (A proxy
   class like this is necessary, because the C++ memory model does not
   include independent addressing of objects smaller than one byte.)
   The public member functions of <tt>reference</tt> are <tt>operator bool() const</tt>,
   <tt>reference&amp; operator=(bool)</tt>, and <tt>void flip()</tt>.  That is, <tt>reference</tt>
   acts like an ordinary reference: you can convert a <tt>reference</tt> to <tt>bool</tt>, 
   assign a <tt>bool</tt> value through a <tt>reference</tt>, or flip the bit that a
   <tt>reference</tt> refers to.
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>size_type capacity() const</tt>
</TD>
<TD VAlign=top>
Number of bits for which memory has been allocated.
   <tt>capacity()</tt> is always greater than or equal to <tt>size()</tt>.
   <A href="#2">[2]</A> <A href="#3">[3]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<tt>void reserve(size_type n)</tt>
</TD>
<TD VAlign=top>
If <tt>n</tt> is less than or equal to <tt>capacity()</tt>, this call has no effect.
    Otherwise, it is a request for the allocation of additional 
    memory.  If the request is successful, then <tt>capacity()</tt> is
    greater than or equal to <tt>n</tt>; otherwise, <tt>capacity()</tt> is unchanged.
    In either case, <tt>size()</tt> is unchanged.  <A href="#2">[2]</A> <A href="#4">[4]</A>
</TD>
</TR>
<TR>
<TD VAlign=top>
<pre>
void swap(bit_vector::reference x,
          bit_vector::reference y)
</pre>
</TD>
<TD VAlign=top>
Swaps the bits referred to by <tt>x</tt> and <tt>y</tt>.  This is a global function,
   not a member function.  It is necessary because the ordinary version
   of <tt><A href="swap.html">swap</A></tt> takes arguments of type <tt>T&amp;</tt>, and <tt>bit_vector::reference</tt>
   is a class, not a built-in C++ reference.
</TD>
</tr>
</table>
<h3>Notes</h3>
<P><A name="1">[1]</A>
This member function relies on <i>member template</i> functions, which
at present (early 1998) are not supported by all compilers.  If your
compiler supports member templates, you can call this function with
any type of <A href="InputIterator.html">input iterator</A>.  If your
compiler does not yet support member templates, though, then the
arguments must either be of type <tt>const bool*</tt> or of type
<tt>bit_vector::const_iterator</tt>.
<P><A name="2">[2]</A>
Memory will be reallocated automatically if more than <tt>capacity() -
size()</tt> bits are inserted into the bit_vector.  Reallocation does
not change <tt>size()</tt>, nor does it change the values of any bits
of the bit_vector.  It does, however, increase <tt>capacity()</tt>,
and it invalidates <A href="#5">[5]</A> any iterators that point into
the bit_vector.
<P><A name="3">[3]</A>
When it is necessary to increase <tt>capacity()</tt>,
<tt>bit_vector</tt> usually increases it by a factor of two.  It is
crucial that the amount of growth is proportional to the current
<tt>capacity()</tt>, rather than a fixed constant: in the former case
inserting a series of bits into a bit_vector is a linear time
operation, and in the latter case it is quadratic.
<P><A name="4">[4]</A>
<tt>reserve()</tt> is used to cause a reallocation manually.  The main
reason for using <tt>reserve()</tt> is efficiency: if you know the
capacity to which your <tt>bit_vector</tt> must eventually grow, then
it is probably more efficient to allocate that memory all at once
rather than relying on the automatic reallocation scheme.  The other
reason for using <tt>reserve()</tt> is to control the invalidation of
iterators. <A href="#5">[5]</A>
<P><A name="5">[5]</A>
A <tt>bit_vector</tt>'s iterators are invalidated when its memory is
reallocated.  Additionally, inserting or deleting a bit in the middle
of a bit_vector invalidates all iterators that point to bits following
the insertion or deletion point.  It follows that you can prevent a
bit_vector's iterators from being invalidated if you use
<tt>reserve()</tt> to preallocate as much storage as the bit_vector
will ever use, and if all insertions and deletions are at the
bit_vector's end.
<h3>See also</h3>
<A href="Vector.html">vector</A>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
